/*
 * @lc app=leetcode.cn id=72 lang=golang
 *
 * [72] 编辑距离
 */

// @lc code=start

func minDistance(word1 string, word2 string) int {
	m, n := len(word1), len(word2)
	dp := make([][]int, m+1)
	for i, _ := range dp {
		dp[i] = make([]int, n+1)
		if i == 0 {
			for j, _ := range dp[i] {
				dp[i][j] = j
			}
		}
		dp[i][0] = i
	}
	for i := 1; i <= m; i++ {
		for j := 1; j <= n; j++ {
			if word1[i-1] == word2[j-1] {
				dp[i][j] = min(dp[i-1][j-1], min(dp[i][j-1], dp[i-1][j])+1)
			} else {
				// 此处记得有替换，也需要比较 dp[i-1][j-1]
				dp[i][j] = min(dp[i-1][j-1], min(dp[i-1][j], dp[i][j-1])) + 1
			}
		}
	}
	return dp[m][n]
}

func min(i, j int) int {
	if i < j {
		return i
	}
	return j
}

// @lc code=end
